#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""
https://blog.csdn.net/m0_37846371/article/details/72854890
https://blog.csdn.net/chenhanzhun/article/details/39895077

也叫"滚动哈希法"
"""

def match(source, pattern):
    digit = 17
    mod   = 1069
    len_s = len(source)
    len_p = len(pattern)

    if len_p > len_s :
        return -1

    digit_expo = (digit ** len_p) % mod

    s_hash = 0
    p_hash = 0
    for i in range(len_p):
        # print('here')
        s_hash = (s_hash * digit + ord(source[i])) % mod
        p_hash = (p_hash * digit + ord(pattern[i])) % mod

    # print(s_hash, p_hash)

    for i in range(0, len_s - len_p+1):
        if s_hash == p_hash:
            # print('here')
            if source[i:i+len_p] == pattern:
                return i
        else:
            if i + len_p < len_s:
                s_hash = (s_hash * digit + ord(source[i+len_p]) - ord(source[i]) * digit_expo) % mod

    return -1


def main():
    print("start main")
    ret = match('preasdfasdfasdf_asdfwetrqwetqwetqwetq', 'asdfwetrqwetqwetqwetq')
    print(ret)

if __name__ == "__main__":
    main()
